package ToYesterday.matixRoute12;

import org.junit.Test;


/*
* 核心：访问某个字符，依次选择向右，向下，向左，向上。符合的入栈下一轮。四个不符合的出栈换个方向。(递归)
边界：当栈为空且四个方向不符合时候，依次寻找。
整体思路：双层循环用于确定第一个，然后再将第一个进入递归，找不到继续双层循环。*/
public class MazeSolution {


    @Test
    public void Testd() {
        char[][] maze = {//i < maze.length,j < maze[0].length;
                {'c', 'c', 'c', 'b', 'b'},
                {'a', 'a', 'b', 'a', 'b'},
                {'c', 'c', 'c', 'a', 'a'},
                {'b', 'a', 'c', 'a', 'a'},
                {'a', 'a', 'b', 'a', 'b'},
                {'c', 'b', 'a', 'a', 'a'},
                {'c', 'b', 'a', 'c', 'c'},
                {'b', 'a', 'a', 'a', 'c'},
                {'c', 'c', 'b', 'a', 'b'},
                {'a', 'b', 'b', 'a', 'b'},
                {'c', 'b', 'c', 'a', 'b'},
                {'b', 'a', 'a', 'c', 'b'}
        };
        String strin = "ccbcccbcaaaab";
        boolean l = Solutiond(maze, strin);
        System.out.println(l);
    }

    public boolean Solutiond(char[][] board, String word) {
        char[] chars = word.toCharArray();
        if (board != null && board[0] != null) {
            boolean[][] booleans = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (SearchMaze(board, i, j, chars, 0, booleans)) return true;
                }
            }
        }
        return false;
    }

    public boolean SearchMaze(char[][] maze, int i, int j, char[] chars, int k, boolean[][] leans) {
        if (i < 0 || j < 0 || i >= maze.length || j >= maze[0].length || leans[i][j] ||maze[i][j] != chars[k] ) {
            return false;
        }
        leans[i][j] = true;
        if (k == (chars.length - 1))
            return true;
        boolean find = SearchMaze(maze, i, j + 1, chars, k + 1, leans) ||
                SearchMaze(maze, i + 1, j, chars, k + 1, leans) ||
                SearchMaze(maze, i, j - 1, chars, k + 1, leans) ||
                SearchMaze(maze, i - 1, j, chars, k + 1, leans);
        if (find) return true;
        leans[i][j] = false;
        return false;
    }

}
